Communication networks generally have messages that are routed among distributed network devices or nodes according to a governing network protocol. The establishment and maintenance of communication routes within a network is an essential part of network management. Various methods have been used for route management depending on network design. In a typical application, routing equipment is placed at key transition points within the network, and such equipment operated according to a set of rules that govern the forwarding of messages from one network device to another. Routing algorithms executed at the routing equipment determine the appropriate paths. The routes, sometimes represented by routing tables, may be established at network setup time, or may be dynamically established through various route discovery techniques.
Ad-hoc networks of wireless devices have been gaining in popularity for certain applications. In an ad-hoc network, the number of nodes, and the communication links among the nodes, may change frequently. Generally, the ad-hoc network is designed to accommodate such dynamic reconfiguration by adjusting communication routes as needed. Some ad-hoc networks are self-organized and have no centralized infrastructure or control mechanism. As a result, there are certain cost, reliability, and robustness advantages that would be inherent in an ad-hoc network, provided that a suitable route management mechanism is available.
A sensor network is one type of network that could benefit from an ad-hoc network design. In a sensor network, sensing devices are distributed about an environment in which monitoring is required. These devices detect or measure some parameter of interest, and report the collected data to one or more reporting stations or collection nodes. An ad-hoc sensor network with a suitable routing mechanism could allow for the collection and reporting of data in a highly reliable and efficient manner. Certain routing mechanisms are known in the art but do not provide an adequate solution for all sensor applications. One example is given in U.S. Pat. No. 6,304,556 issued to Haas on Oct. 16, 2001, and entitled “ROUTING AND MOBILITY MANAGEMENT PROTOCOLS FOR AD-HOC NETWORKS”. Here, the network is divided into overlapping routing zones, and each node is required to know the topology of the network within its routing zone. Route discovery inquiries are limited to those nodes located on the periphery of routing zones in an attempt to reduce overhead. However, a significant amount of overhead still remains in the route discovery process. Another example is described in U.S. Pat. No. 5,490,139 issued to Baker et al., on Feb. 6, 1996, and entitled “MOBILITY ENABLING ACCESS POINT ARCHTECTURE FOR WIRELESS ATTACHMENT TO SOURCE ROUTING NETWORKS”. Here, a token ring network is used as a means of transporting packets. Usually, a route discovered for every destination is stored in local memory and used for every packet that is sent to that destination. However, such routing mechanism requires the availability of a large amount of processing and memory resources.
Recently, there have been attempts to develop routing algorithms for telecommunication networks using Ant Colony Optimization (ACO) heuristics. One such approach is described in a paper entitled “A NEW DYNAMIC DISTRIBUTED ROUTING ALGORITHM ON TELECOMMNICATION NETWORKS” published by Lianyan Li, Zemin Liu and Zheng Zhou in the Institute of Electrical and Electronics Engineers (IEEE) Communication Technology Proceedings, WCC-ICCT 2000. In this approach, pheromone tables, which are tables of probabilities, replace traditional routing tables. To update the tables, agents, intended to model the behavior of ants, are launched from every node in the network at each time step, and at launch time, each agent is assigned a random destination node. At a particular node, the agent selects the next node on the route according to a particular probability algorithm. The agent records every node that it passes, and if the node reaches its destination, the pheromone tables at the nodes that the agent has visited are updated. After the update of the pheromone tables, more agents will select the shorter routes or travel along paths with better load conditions. In another paper published by Ying Wang and Jianying Xie, at the 2000 IEEE APCCAS Conference, and entitled “ANT COLONY OPTIMIZATION FOR MULTICAST ROUTING”, a multicast routing algorithm is proposed that purports to shown improved effectiveness and capability of parallel implementation.
While prior art techniques, including ant colony modeling, may be applicable to routing problems in communication networks, the techniques have not been adequately developed to satisfactorily address data collection and routing requirements present in sensor networks and many other types of communication networks. Accordingly, a new approach to route discovery and data collection in networks is needed.